π§· μ΄λΆ νμ
νμ λ²μλ₯Ό λ λΆλΆμΌλ‘ λΆν νλ©΄μ μ°Ύλ λ°©μ
- μ²μλΆν° λκΉμ§ νμνλ κ²λ³΄λ€ λ λΉ λ₯Έ μκ° λ³΅μ‘λλ₯Ό κ°μ§λ λ°©μ
**μκ° λ³΅μ‘λ**
μ 체 νμ: O(N)
μ΄λΆ νμ: O(logN)
πͺ κ³Όμ
κ°μ₯ ν΅μ¬μ μ λ ¬μ΄ λμ΄ μμ΄μΌ νλ€λ μ μ΄λ€.
leftμrightλ₯Ό μ¬μ©ν΄midλ₯Ό μ€μ νλ€.-
midμ ꡬνκ³ μ νλ κ°μ λΉκ΅νλ€.- ꡬνκ³ μ νλ κ°μ΄ λ ν° κ²½μ°,
left = mid + 1 - λ μμ κ²½μ°,
right = mid - 1
- ꡬνκ³ μ νλ κ°μ΄ λ ν° κ²½μ°,
left > rightκ° λ λκΉμ§ λ°λ³΅- νμν λ°°μ΄μ λ²μλ₯Ό λ²μ΄λλ€λ©΄, ꡬνκ³ μ νλ κ°μ΄ λ°°μ΄μ μμμ νλ¨ν μ μλ€.
int binarySearch(int[] numbers, int M) {
Arrays.sort(numbers);
int left = 0;
int right = numbers.length - 1;
int mid;
while (left < right) {
mid = (left + right) / 2;
if (numbers[mid] == M)
return mid;
else if (numbers[mid] < M)
left = mid + 1;
else
right = mid - 1;
}
}
πͺ μΆκ° μμ
μ΄λΆ νμμ μ λ ¬λ λ°μ΄ν°μμ νΉμ κ°μ μ°Ύκ³ μ ν λ λΉ λ₯Έ μκ° λ³΅μ‘λλ‘ νμμ΄ κ°λ₯νλ€λ μ₯μ μ΄ μλ€. μ΄λ₯Ό μ΄μ©ν΄ μ μ Nμ΄ μ£Όμ΄μ‘μ λ, Nμ μ κ³±κ·Όμ ꡬνλ μ½λλ₯Ό μμ±ν΄λ³Έλ€.
- 1λΆν° μ£Όμ΄μ§ μ μκΉμ§μ λ¨μ λ°λ³΅ λ° νμΈμΌλ‘ ꡬν μλ μμ§λ§ μ΄λ μ μκ° λ³΅μ‘λλ₯Ό κ°μ§λ€.
μ΄λ₯Ό μ΄λΆ νμμ μ¬μ©νμ¬ "0λΆν° NκΉμ§μ μμ°μ μ€ Nμ μ κ³±κ·Όμ΄ μλμ§ μλμ§" νμΈνλ μ½λλ‘ λ³κ²½νλ€. μ¦, 0λΆν° NκΉμ§μ μ λ ¬λ μμ°μ μ€μμ νΉμ κ°μ μ°Ύκ³ μλ κ²μ΄λ€.
int squareRootSearch(int M) {
int left = 0;
int right = M;
int num, squareNum;
while (left < right) {
num = (left + right) / 2;
squareNum = num * num;
if (squareNum == M)
return num;
else if (squareNum < M)
left = num + 1;
else
right = num - 1;
}
}